The present invention relates in general to computer rendering technologies, and in particular to techniques for diamond culling of small primitives.
Computer-based rendering systems generally receive image data in the form of primitives (such as lines or triangles) that represent objects to be drawn. After transforming the primitives to a viewing space, the primitives are rasterized to generate pixel data values. Rasterization generally involves determining, for each pixel, which primitive should be seen on the screen and shading the pixel based on attributes of that primitive. As one aspect of this process, it is generally necessary to determine which of the primitives cover a given pixel. In some cases, multiple primitives may cover the same pixel, and the rasterizer selects among them, e.g., by identifying which is closest to the eyepoint.
One challenge in determining coverage is the case where a primitive covers only part of a pixel. For example, a line is generally less than a pixel wide; in the case of a triangle, pixels along the edges may be only partially covered by the triangle. Coverage rules are generally prescribed for handling such cases in a consistent manner. For example, for rasterizing triangles, one commonly used coverage rule provides that a triangle covers a pixel only if it covers the center point of the pixel.
For rasterizing lines, a center coverage rule is usually not optimal, and other rules are often used instead. For instance, the widely used OpenGL standard specifies a “diamond exit rule,” illustrated in FIG. 1. Each pixel 101-109 has a diamond 111-119 (dashed lines) inscribed therein, centered on the pixel center. A line to be rasterized is defined by specifying a start vertex and an end vertex. According to the diamond exit rule, the line covers (or “hits”) the pixel and should be drawn in that pixel only if the line (going from start vertex to end vertex) exits the diamond for that pixel. For instance, FIG. 1 shows three lines 122, 124, 126, with the direction of drawing for each line indicated by an arrowhead. Line 122 hits pixels 103 and 102 because it exits diamonds 113 and 112. (Hit pixels are indicated by shaded diamonds in FIG. 1) Line 124 hits pixels 104 and 105 but not pixel 106 because it enters diamond 116 but does not exit. Line 126 hits only pixel 108 because it exits only diamond 118. It should be noted that the diamond exit rule is dependent on the direction of drawing; for example, if line 126 were drawn in the other direction, it would hit both of pixels 109 and 108. Small lines might not exit any diamonds; such lines would not be visible on the screen.
Complex images, such as those typically found in 3D video games or other applications, involve a very large number of primitives, and one of the factors that limits rendering speed is the time needed for the rasterizer to process all of the primitives. Thus, rendering pipelines usually include a culling stage intended to reduce the number of primitives that the rasterizer processes. For example, it is common to define a view frustum that bounds a visible region of the 3D space. Any primitive that lies entirely outside this region will not be seen and can be culled from the geometry data prior to rasterization.
But some primitives inside the view frustum could also be culled, at least in theory, because they turn out not to cover any pixels. For example, a small triangle might not cover any pixel centers, or a short line might not exit any diamonds. Such primitives are invisible, having no effect on the rendered image. Existing culling techniques generally do not systematically identify or cull such primitives, due in part to a lack of computationally efficient ways to identify and cull all such primitives without also culling some primitives that should be drawn. Thus, the rasterizer may process a significant number of primitives that do not actually cover any pixels, which results in slower rendering.
It would therefore be desirable to provide improved culling techniques for identifying and eliminating invisible small primitives.